package leetcode.code0109;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;
import leetcode.helper.tree.ListNode;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	public TreeNode sortedListToBST(ListNode head) {
		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return new TreeNode(head.val);
		}
		ListNode fast = head;
		ListNode slow = head;
		ListNode tail = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			if (fast == null || fast.next == null || fast.next.next == null) {
				tail = slow;
			}
			slow = slow.next;
		}
		ListNode next = slow == null ? null : slow.next;
		tail.next = null;
		TreeNode root = new TreeNode(slow.val);
		root.left = this.sortedListToBST(head);
		root.right = this.sortedListToBST(next);
		return root;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.sortedListToBST(ListNode.set(HelpDebug.str2array3("[-10,-3,0,5,9]")));

	}

}
